package org.example.day;

/**
 * @Description: TODO
 * @Author wyatt
 * @Data 2024/06/27 9:58
 */
//给你一个仅由小写英文字母组成的字符串 s 。在一步操作中，你可以完成以下行为：
//
//
// 选择 s 的任一非空子字符串，可能是整个字符串，接着将字符串中的每一个字符替换为英文字母表中的前一个字符。例如，'b' 用 'a' 替换，'a' 用
//'z' 替换。
//
//
// 返回执行上述操作 恰好一次 后可以获得的 字典序最小 的字符串。
//
// 子字符串 是字符串中的一个连续字符序列。 现有长度相同的两个字符串
//x 和 字符串
//y ，在满足
//x[i] != y[i] 的第一个位置
//i 上，如果
//x[i] 在字母表中先于
//y[i] 出现，则认为字符串
//x 比字符串
//y
//字典序更小 。
//
//
//
// 示例 1：
//
//
//输入：s = "cbabc"
//输出："baabc"
//解释：我们选择从下标 0 开始、到下标 1 结束的子字符串执行操作。
//可以证明最终得到的字符串是字典序最小的。
//
//
// 示例 2：
//
//
//输入：s = "acbbc"
//输出："abaab"
//解释：我们选择从下标 1 开始、到下标 4 结束的子字符串执行操作。
//可以证明最终得到的字符串是字典序最小的。
//
//
// 示例 3：
//
//
//输入：s = "leetcode"
//输出："kddsbncd"
//解释：我们选择整个字符串执行操作。
//可以证明最终得到的字符串是字典序最小的。
//
//
//
//
// 提示：
//
//
// 1 <= s.length <= 3 * 10⁵
// s 仅由小写英文字母组成
//
//
// Related Topics 贪心 字符串 👍 21 👎 0


public class Solution2734 {

    public static void main(String[] args) {
        String[] subStrArr = "".split("a");
        for (int i = 0; i < subStrArr.length; i++) {
            System.out.println(subStrArr[i]);
        }

        System.out.println(new Solution2734().smallestString(""));
        System.out.println(new Solution2734().smallestString("aaa"));
        System.out.println(new Solution2734().smallestString("bbba"));
        System.out.println(new Solution2734().smallestString("acac"));
        System.out.println(new Solution2734().smallestString("caca"));
        System.out.println(new Solution2734().smallestString("aaaacccc"));
        System.out.println(new Solution2734().smallestString("cccccaaaaa"));
        System.out.println(new Solution2734().smallestString("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" +
                "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" +
                "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" +
                "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" +
                "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" +
                "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" +
                "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" +
                "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" +
                "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" +
                "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" +
                "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" +
                "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" +
                "" +
                ""));
    }

    @Deprecated
    public String smallestString(String s) {
        if(s.contains("a")){
            boolean letter = false;
            int end = 0;
            int start = 0;
            StringBuilder result = new StringBuilder();
            for (int i = 0; i < s.toCharArray().length; i++) {
                end = i;
                if(s.charAt(i) == 'a'){
                    if(letter){
                        end--;
                        break;
                    }else {
                       start++;
                    }
                }else {
                    if(!letter){
                        letter = true;
                    }
                    result.append((char)(s.charAt(i)-1));
                }
            }
            if(end < s.length() -1){
                result.append(s.substring(end+1));
            }
            String startStr = "";
            if(start > 0){
                startStr = s.substring(0, start);
            }
            if(!letter){
                //全部是a 替换最后一个a
                return startStr + result.toString().substring(0, result.length()-1) + 'z';
            }
            return startStr + result.toString();
        }else {
            StringBuilder result = new StringBuilder();
            for (int i = 0; i < s.toCharArray().length; i++) {
                result.append((char) (s.charAt(i) - 1));
            }
            return result.toString();
        }
    }

    public String smallestString2(String s) {
        int indexOfFirstNonA = findFirstNonA(s);
        if (indexOfFirstNonA == s.length()) {
            StringBuilder sb = new StringBuilder(s);
            sb.setCharAt(s.length() - 1, 'z');
            return sb.toString();
        }
        int indexOfFirstA_AfterFirstNonA = findFirstA_AfterFirstNonA(s, indexOfFirstNonA);
        StringBuilder res = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (i >= indexOfFirstNonA && i < indexOfFirstA_AfterFirstNonA) {
                res.append((char) (c - 1));
            } else {
                res.append(c);
            }
        }
        return res.toString();
    }

    public int findFirstNonA(String s) {
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) != 'a') {
                return i;
            }
        }
        return s.length();
    }

    public int findFirstA_AfterFirstNonA(String s, int firstNonA) {
        for (int i = firstNonA; i < s.length(); i++) {
            if (s.charAt(i) == 'a') {
                return i;
            }
        }
        return s.length();
    }
}
// 作者：力扣官方题解
// 链接：https://leetcode.cn/problems/lexicographically-smallest-string-after-substring-operation/solutions/2821506/zhi-xing-zi-chuan-cao-zuo-hou-de-zi-dian-ugxd/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
